package main.java.indi.zyj.sort;

import java.util.Arrays;

public class HeapSort {

    //堆排序
    private static void heapSort(int[] tree, int n) {
        buildHeap(tree, n);
        for (int i = n - 1; i >= 0; i--) {
            swap(tree, 0, i);//把最大的放最后面
            adjust(tree, 0, i);//调整
        }
    }

    //构建最大堆
    private static void buildHeap(int[] tree, int n) {
        // 获取最后一个节点
        int lastNode = tree.length - 1;
        // 获取最后的父节点
        int parent = (lastNode - 1) / 2;
        //从下往上构建
        for (int i = parent; i >= 0; i--) {
            adjust(tree, i, n);
        }
    }

    //在左子节点，右子节点中找出最大值与父节点替换，形成局部最大堆
    private static void adjust(int[] tree, int i, int n) {
        int max = i;
        int c1 = 2 * i + 1;     // 左孩子
        int c2 = 2 * i + 2;     // 右孩子
        if (c1 < n && tree[c1] > tree[max]) {
            max = c1;
        }
        if (c2 < n && tree[c2] > tree[max]) {
            max = c2;
        }
        if (max != i) {
            // 让最大的那个子节点做父亲，交换后max是小值
            swap(tree, i, max);
            // 交換下标后下坠
            adjust(tree, max, n);
        }
    }

    //交换
    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] tree = {2, 5, 3, 1, 10, 4};
        heapSort(tree, tree.length);
        System.out.println(Arrays.toString(tree));//[1, 2, 3, 4, 5, 10]
    }


}
